package com.wangjw.leetcode;


import java.util.*;

/**
 * Created by wangjw on 18/6/28.
 */
public class LeetCode347 {

    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>(
                (a, b) -> map.get(a) - map.get(b)
        );
        for (int key : map.keySet()) {
            if (pq.size() < k) {
                pq.add(key);
            } else if (map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }
        }

        List<Integer> res = new ArrayList<>();
        while (!pq.isEmpty()) {
            res.add(pq.remove());
        }
        return res;
    }

    public static void main(String[] args) {
        LeetCode347 leetCode347 = new LeetCode347();
        int[] arr = {5,3,1,1,1,3,73,1};
        List<Integer> list = leetCode347.topKFrequent(arr, 2);

        for (int num : list) {
            System.out.print(num + " ");
        }
    }
}
